#include<bits/stdc++.h>
using namespace std;

// Class T must has operator < (but need not have operator > and ==)
template <class T>
class Splay {
private:
	struct node {
		T val;
		int cnt;
		node * fa, * son[2];
		#define lson son[0]
		#define rson son[1]
		node(const T & _val, node * _fa, node * _lson, node * _rson, int _cnt = 1) : val(_val), cnt(_cnt), fa(_fa) {lson = _lson, rson = _rson;}
	};
	
	// Clear u and the subtree of u.
	void clear(node *& u) {
		if(u == nullptr) return;
		clear(u -> lson);
		clear(u -> rson);
		delete u;
		u = nullptr;
	}
	
	node * root;
	
	// Make node u take the place of its father.
	inline void rotate(node *& u) {
		node * v = u -> fa, * r = v -> fa;
		bool op = u == v -> rson;
		u -> fa = r;
		if (r == nullptr) root = u;
		else r -> son[v == r -> rson] = u;
		if (u -> son[op ^ 1] != nullptr) u -> son[op ^ 1] -> fa = v;
		v -> son[op] = u -> son[op ^ 1];
		v -> fa = u;
		u -> son[op ^ 1] = v;
	}
	
	// Rotate the node u until it become the root. Balance the tree in the process.
	inline void splay(node * u){
		if (u == nullptr) return;
		while (u != root) {
			node * v = u -> fa, * r = v -> fa;
			if (v != root) {
				if ((u == v -> rson) ^ (v == r -> rson)) rotate(u);
				else rotate(v);
			}
			if (u != root) rotate(u);
		}
	}
	
	// Insert the number val.
	void insert(const T & val, node *& u, node * f = nullptr) {
		if (u == nullptr) {
			u = new node(val, f, nullptr, nullptr);
			splay(u);
			return;
		}
		if (val < u -> val) insert(val, u -> lson, u);
		else if (u -> val < val) insert(val, u -> rson, u);
		else ++u -> cnt;
	}
	
	// Iterate the Splay Tree, and put all the elements into the vector v.
	void to_vector(vector <T> & v, node * u) {
		if (u == nullptr) return;
		to_vector(v, u -> lson);
		for (int i = 0; i < u -> cnt; ++i) v.push_back(u -> val);
		to_vector(v, u -> rson);
	}
	
public:
	Splay(){
		root = nullptr;
	}
	~Splay() {
		clear(root);
	}
	void insert(const T & val) {
		insert(val, root);
	}
	void to_vector(vector <T> & data) {
		to_vector(data, root);
	}
};

template <class T>
void Splay_sort(vector <T> & data){
	Splay <T> t;
	for(int i = 0; i < data.size(); ++i) t.insert(data[i]);
	data.clear();
	t.to_vector(data);
}